/**
 * @Author: wangy
 * @Date: 2022-04-18 15:43:57
 * @Description: 树结构封装
 * @Copyright (c) 2022 by wangy, All Rights Reserved.
 */

// 创建节点类
class Node {
	constructor(key) {
		this.key = key;
		this.left = null;
		this.right = null;
	}
}

// 封装二叉搜索树（特点：左子树节点值 < ）
export class BinarySearchTree {
	constructor() {
		this.root = null;
	}

	/*******
	 * @description: 插入数据
	 * @param {*} key
	 * @return {*}
	 */
	insert(key) {
		const newNode = new Node(key);

		if (this.root === null) {
			this.root = newNode;
		} else {
			this.insertNode(this.root, newNode);
		}
	}

	insertNode(root, node) {
		if (node.key < root.key) {
			// 往左边查找插入
			if (root.left === null) {
				root.left = node;
			} else {
				this.insertNode(root.left, node);
			}
		} else {
			// 往右边查找插入
			if (root.right === null) {
				root.right = node;
			} else {
				this.insertNode(root.right, node);
			}
		}
	}

	// ----------- 二叉树遍历 ----------//
	/*******
	 * @description: 先序遍历（根左右DLR）
	 * @return {*} result
	 */
	preorderTraversal() {
		const result = [];
		this.preorderTraversalNode(this.root, result);
		return result;
	}

	preorderTraversalNode(node, result) {
		if (node === null) return result;
		result.push(node.key);
		this.preorderTraversalNode(node.left, result);
		this.preorderTraversalNode(node.right, result);
	}

	/*******
	 * @description: 中序遍历（左根右LDR）
	 * @return {*} result
	 */
	inorderTraversal() {
		const result = [];
		this.inorderTraversalNode(this.root, result);
		return result;
	}

	inorderTraversalNode(node, result) {
		if (node === null) return result;
		this.inorderTraversalNode(node.left, result);
		result.push(node.key);
		this.inorderTraversalNode(node.right, result);
	}

	/*******
	 * @description: 后序遍历（左右根 LRD）
	 * @return {*} result
	 */
	postorderTraversal() {
		const result = [];
		this.postorderTraversalNode(this.root, result);
		return result;
	}

	postorderTraversalNode(node, result) {
		if (node === null) return result;
		this.postorderTraversalNode(node.left, result);
		this.postorderTraversalNode(node.right, result);
		result.push(node.key);
	}

	/*****
	 * @description: 获取二叉搜索树最小值
	 * @return {*} node.key
	 */
	min() {
		if (!this.root) return null;
		let node = this.root;
		while (node.left !== null) {
			node = node.left;
		}
		return node.key;
	}

	/*******
	 * @description:获取二叉搜索树最大值
	 * @return {*} node.key
	 */
	max() {
		if (!this.root) return null;
		let node = this.root;
		while (node.right !== null) {
			node = node.right;
		}
		return node.key;
	}

	/*******
	 * @description: 查找二叉搜索树中是否有相同的key
	 * @param {*} key
	 * @return {*}
	 */
	search(key) {
		return this.searchNode(this.root, key);
	}

	// 通过递归实现
	searchNode(node, key) {
		if (node === null) return false;
		if (key < node.key) {
			return this.searchNode(node.left, key);
		} else if (key > node.key) {
			return this.searchNode(node.right, key);
		} else {
			return true;
		}
	}

	/*******
	 * @description: 通过 while 循环实现
	 * @param {*} key
	 * @return {*}
	 */
	search2(key) {
		let node = this.root;

		while (node !== null) {
			if (key < node.key) {
				node = node.left;
			} else if (key > node.key) {
				node = node.right;
			} else {
				return true;
			}
		}

		return false;
	}

	/*******
	 * @description: 删除节点
	 * @param {*} key
	 * @return {*}
	 */
	remove(key) {
		let currentNode = this.root;
		let parentNode = null;
		let isLeftChild = true;

		// 循环查找到要删除的节点 currentNode，以及他的 parentNode、isLeftChild
		while (currentNode.key !== key) {
			parentNode = currentNode;

			// 小于，往左查找
			if (key < currentNode.key) {
				isLeftChild = true;
				currentNode = currentNode.left;
			} else {
				// 否则往右查找
				isLeftChild = false;
				currentNode = currentNode.right;
			}

			// 找到最后没找到相等的节点，返回 false
			if (currentNode === null) {
				return false;
			}
		}

		// 1.删除的是叶子结点的情况
		if (currentNode.left === null && currentNode.right === null) {
			if (currentNode === this.root) {
				this.root = null;
			} else if (isLeftChild) {
				parentNode.left = null;
			} else {
				parentNode.right = null;
			}

			// 2.删除的是只是一个子节点的节点
		} else if (currentNode.right === null) {
			// currentNode 只存在左节点
			// 2.1、currentNode 只存在<左节点>的情况
			// 2.1.1、currentNode 等于root
			// 2.1.2、parentNode.left等于currentNode
			// 2.1.3、parentNode.right等于currentNode

			if (currentNode === this.root) {
				this.root = currentNode.left;
			} else if (isLeftChild) {
				parentNode.left = currentNode.left;
			} else {
				parentNode.right = currentNode.left;
			}
		} else if (currentNode.left === null) {
			// 2.2、currentNode 只存在<右节点>的情况
			// 2.1.1、currentNode 等于root
			// 2.1.2、parentNode.left 等于 currentNode
			// 2.1.1、parentNode.rigth 等于 currentNode

			if (currentNode === this.root) {
				this.root = currentNode.right;
			} else if (isLeftChild) {
				parentNode.left = currentNode.right;
			} else {
				parentNode.right = currentNode.right;
			}

			// 3.删除的是有两个子节点的节点
		} else {
			// 1.找到后续节点
			let successor = this.getSuccessor(currentNode);

			// 2.判断是否为根结点
			if (currentNode === this.root) {
				this.root = successor;
			} else if (isLeftChild) {
				parentNode.left = successor;
			} else {
				parentNode.right = successor;
			}

			// 3.将后续的左节点改为被删除的左节点
			successor.left = currentNode.left;
		}
	}

	/*******
	 * @description: 获取后续节点，即从要删除的节点的右边开始查找最小值
	 * @param {*} delNode
	 * @return {*}
	 */
	getSuccessor(delNode) {
		// 定义变量，保存要找到的后续
		let successor = delNode;
		let current = delNode.right;
		let successorParent = delNode;

		// 循环查找 current 的右子树结点
		while (current !== null) {
			successorParent = successor;
			successor = current;
			current = current.left;
		}

		// 判断寻找到的后续节点是否直接就是要删除节点的 right
		if (successor !== delNode.right) {
			successorParent.left = successor.right;
			successor.right = delNode.right;
		}
		return successor;
	}
}
